package com.liang.leetcode.dp;

import java.util.Arrays;

/**
 * 322.零钱兑换 -- 完全背包问题，装满背包最少的物品个数
 * 凑成总金额的凑法中，需要硬币最少的个数是多少
 */
public class Dp10_CoinChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange2(coins, amount));
    }

    /**
     * 解法1：动态规划
     * <p>
     * 面值  0  1  2   3   4    5
     * 1   0  1  11 111 1111 11111
     * 2   0  1  2  21  22   221
     * 5   0  1  2  21  22   5
     * <p>
     * 总金额       类比背包容量
     * 硬币面值     类比物品重量
     * 硬币个数     类比物品价值，固定为1（求价值(个数)最小）
     * <p>
     * if(装得下){
     *      min(上次价值(个数)，剩余容量能装下的最小价值(个数) + 1)
     *      min(dp[i-1][j], dp[i][j-coin[i]] + 1)
     * } else {
     *      保留上次价值(个数)不变
     *      dp[i][j] = dp[i-1][j]
     * }
     */
    private static int coinChange(int[] coins, int amount) {
        // 硬币个数
        int n = coins.length;
        // dp[i][j] 表示使用前 i 种硬币凑成金额 j 的最小硬币数量
        int[][] dp = new int[n][amount + 1];
        // 初始化dp数组第一行
        for (int j = 1; j <= amount; j++) {
            // 使用第一种硬币凑成金额 j 的数量
            if (j >= coins[0]) {
                dp[0][j] = dp[0][j - coins[0]] + 1;
            } else {
                // 凑不齐（硬币金额多了或少了），设置为不可达的大数
                dp[0][j] = amount + 1;
            }
        }
        // 遍历 i 个硬币
        for (int i = 1; i < n; i++) {
            // 遍历总金额 j
            for (int j = 1; j <= amount; j++) {
                // 当前金额 j 大于当前硬币面值 coins[i]，选择使用或者不使用当前硬币
                if (j >= coins[i]) {
                    // 取不使用第 i 种硬币和使用第 i 种硬币两种情况中的最小值
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i]] + 1);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][amount] < amount + 1 ? dp[n - 1][amount] : -1;
    }

    /**
     * 滚动数组降维优化
     */
    private static int coinChange2(int[] coins, int amount) {
        // dp[j] 表示凑成金额 j 的最小硬币数量
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        // 遍历硬币 i，[1,2,5]
        for (int i = 0; i < coins.length; i++) {
            // 遍历金额 j 到 amount 11
            for (int j = coins[i]; j <= amount; j++) {
                // 更新 dp[j]，选择使用当前硬币或者不使用的最小硬币数量
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] < amount + 1 ? dp[amount] : -1;
    }
}
